#include <bits/stdc++.h>

using namespace std;

typedef struct LNode {
    char data;
    struct LNode *next;
}LNode, *LinkedList;

bool Init(LinkedList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    if (L == NULL)
        return false;
    return true;
}

bool Insert(LinkedList &L, char c) {
    LNode *p = L;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = c;
    while (p->next != NULL)
        p = p->next;
    p->next = s;
    s->next = NULL;
    return true;
}

void PrintList(LinkedList L) {
    LNode *p = L;
    cout << "LinkedList:";
    while (p->next != NULL) {
        p = p->next;
        if (p->next == NULL)
            cout << p->data;
        else
            cout << p->data << "->";
    }
    cout << endl;
}

int Length(LinkedList L) {
    LNode *p = L;
    int count = 0;
    while (p->next != NULL) {
        p = p->next;
        count++;
    }
    return count;
}

LNode* find_addr(LinkedList str1, LinkedList str2) {
    int n = Length(str1), m = Length(str2);
    LNode *p = str1, *q = str2;
    if (n > m)
        for (int i = 0; i < (n - m); i++)
            p = p->next;
    else
        for (int i = 0; i < (m - n); i++)
            q = q->next;
    while (p->next != NULL && q->next != NULL) {
        p = p->next;
        q = q->next;
        if (p == q)
            return p;
    }
    return NULL;
}

int main() {
    char ch1[] = "loading";
    char ch2[] = "being";
    LinkedList str1;
    LinkedList str2;
    Init(str1);
    Init(str2);
    for (int i = 0; i < 4; i++)
        Insert(str1, ch1[i]);
    for (int i = 0; i < 2; i++)
        Insert(str2, ch2[i]);
    // 构造链表“ing”并分别添加至str1与str2末尾
    LinkedList temp;
    Init(temp);
    Insert(temp, 'i');
    Insert(temp, 'n');
    Insert(temp, 'g');
    LNode *p = str1;
    while (p->next != NULL)
        p = p->next;
    // 注意要跳过temp的头结点
    p->next = temp->next;
    p = str2;
    while (p->next != NULL)
        p = p->next;
    // 注意要跳过temp的头结点
    p->next = temp->next;
    cout << "Input:" << endl;
    PrintList(str1);
    PrintList(str2);
    // 输出看下结果
    cout << "result:" << endl;
    LNode* res = find_addr(str1, str2);
    if (res != NULL)
        cout << res->data << endl;
    else
        cout << "NULL" << endl;
    return 0;
}